package com.zjj.learn.algorithmPlus.segment1.linklist;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * 单向链表
 * 有哨兵节点，哨兵节点是 head 节点，head 节点后面的数据才是真正的数据
 *
 * @author zjj_admin
 */
public class SinglyLinkedListSentinel implements Iterable<Integer> {

    /**
     * 链表头指针，这里头结点是哨兵，没有含义
     */
    private Node head = new Node(Integer.MIN_VALUE, null);

    /**
     * 在链表的头部插入一个数据，不需要考虑头结点为 null 的情况了
     *
     * @param value 待插入数据
     */
    public void addFirstInitial(int value) {

        //定义当前节点
        Node curr = new Node(value, null);
        //head 节点是哨兵节点
        curr.next = head.next;
        head.next = curr;
    }


    /**
     * 遍历链表，使用函数式接口 Consumer
     */
    public void loopWhile(Consumer<Integer> consumer) {
        Node p = head.next;
        //当前节点不为 null 就一直循环
        while (p != null) {
            // accept 里面传入相关的参数
            consumer.accept(p.value);
            p = p.next;
        }
    }

    /**
     * 遍历链表，使用函数式接口 Consumer
     */
    public void loopFor(Consumer<Integer> consumer) {
        //使用基于 for 循环遍历
        for (Node p = head.next; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }


    /**
     * 在链表的头部插入一个数据
     *
     * @param value 待插入数据
     */
    public void addFirst(int value) {
        //可以将上面的代码进行简化
        head.next = new Node(value, head.next);
    }


    /**
     * 添加数据到尾结点
     *
     * @param value
     */
    public void addLast(int value) {
        Node last = findLast();
        //将当前数据节点存放到 last 的 next 指针
        last.next = new Node(value, null);
    }

    /**
     * 找到当前链表的最后一个节点
     *
     * @return
     */
    private Node findLast() {
        Node p = head;
        //依次遍历，当当前节点 的 next 指针为 null 时，就表示是最后一个节点了
        while (p.next != null) {
            p = p.next;
        }
        return p;
    }

    /**
     * 获取链表的长度
     *
     * @return
     */
    public int size() {
        int size = 0;
        Node p = head.next;
        while (p != null) {
            size++;
            p = p.next;
        }
        return size;
    }

    /**
     * 获取链表中的所有数据
     *
     * @return 数据数组
     */
    public int[] values() {
        //获取链表长度
        int size = size();
        int[] nums = new int[size];
        //索引从 0 开始
        int i = 0;
        Node p = head.next;
        while (i < size) {
            nums[i] = p.value;
            p = p.next;
            i++;
        }
        return nums;
    }


    /**
     * 获取索引为 index 对应节点的数据
     *
     * @param index
     * @return
     */
    public int get(int index) {
        Node node = getNode(index);
        if (null == node) {
            throw new IndexOutOfBoundsException("index：" + index + " 越界了");
        }
        return node.value;
    }


    /**
     * 获取索引为 index 对应节点
     * 哨兵节点的索引为 -1，真实节点的索引从 0 开始
     *
     * @param index
     * @return
     */
    private Node getNode(int index) {
        int i = -1;
        Node p = head;
        while (p != null) {
            //只要当 i 和索引相等时就可以反悔了
            if (i == index) {
                return p;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    /**
     * 在链表的指定位置插入数据，详细代码
     *
     * @param index 位置索引
     * @param value 插入数据
     */
    public void addInitial(int index, int value) {
        //获取上一个节点
        Node prev = getNode(index - 1);
        if (prev == null) {
            throw new IndexOutOfBoundsException("index：" + index + " 越界了");
        }
        //当前需要插入的节点
        Node curr = new Node(value, null);
        //让当前节点的 next 指针指向 prev 的 next
        curr.next = prev.next;
        prev.next = curr;
    }

    /**
     * 在链表的指定位置插入数据，精简代码
     *
     * @param index 位置索引
     * @param value 插入数据
     */
    public void add(int index, int value) {
        //获取上一个节点
        Node prev = getNode(index - 1);
        if (prev == null) {
            throw new IndexOutOfBoundsException("index：" + index + " 越界了");
        }
        //当前需要插入的节点
        prev.next = new Node(value, prev.next);
    }

    /**
     * 删除第一个节点
     *
     * @return 被删除的索引节点数据
     */
    public int removeFirst() {
        if (head.next == null) {
            throw new IndexOutOfBoundsException("没有数据了...");
        }
        int v = head.next.value;
        head.next = head.next.next;
        return v;
    }

    /**
     * 根据索引数据
     *
     * @param index 删除索引
     * @return 被删除的索引节点数据
     */
    public int remove(int index) {
        //获取被删除节点的上一个节点
        Node prev = getNode(index - 1);
        if (prev == null) {
            throw new IndexOutOfBoundsException("index " + index + " 越界了...");
        }
        Node removed = prev.next;
        if (removed == null) {
            throw new IndexOutOfBoundsException("index " + index + " 越界了...");
        }
        int v = removed.value;
        //只需要将被删除节点的上一个节点的 next 指针指向被删除节点的 next 指针就可以了
        prev.next = removed.next;
        return v;
    }

    /**
     * 基于迭代器进行循环
     *
     * @return
     */
    @Override
    public Iterator<Integer> iterator() {

        /**
         * 匿名内部类
         */

        return new Iterator<Integer>() {
            Node p = head.next;

            /**
             * 是否存在下一个元素
             * @return
             */
            @Override
            public boolean hasNext() {
                return p != null;
            }

            /**
             * 返回当前数据，并指向下一个元素
             * @return
             */
            @Override
            public Integer next() {
                int v = p.value;
                p = p.next;
                return v;
            }
        };
    }

    /**
     * 链表中的节点，链表和节点是组合的关系，所以做成内部内比较合适。
     * <p>
     * static 关键字为什么要加？什么时候应该使用 static ？
     * ---- 当内部类中没有引用外部类的成员变量时，就推荐加 static。
     * ---- 当内部类中有引用外部类的成员变量时，就一定不能加 static。
     */
    private static class Node {
        /**
         * 节点数据
         */
        int value;

        /**
         * 当前节点的下一个指针
         */
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

}
